#! /usr/bin/env python
# -*- coding: utf-8 -*-

# Copyright (c) Huoty, All rights reserved
# Author: Huoty <sudohuoty@163.com>
# CreateTime: 2020-04-16 12:15:25

import random


def binary_search_recurse(array, value, left=0, right=None):
    if right is None:
        right = len(array) - 1

    if left > right:
        return None

    mid = (left + right) // 2
    if array[mid] < value:
        return binary_search_recurse(array, value, mid + 1, right)
    elif array[mid] > value:
        return binary_search_recurse(array, value, left, mid - 1)
    else:
        return mid


def binary_search_loop(array, value):
    left = 0
    right = len(array) - 1
    while left <= right:
        mid = (left + right) // 2
        if array[mid] < value:
            left = mid + 1
        elif array[mid] > value:
            right = mid - 1
        else:
            return mid
    return None


def gen_random_data(length=10, mix=0, max=100):
    return [random.randint(mix, max) for _ in range(length)]


if __name__ == "__main__":
    arr = sorted(gen_random_data(25))
    print("Array:", arr)
    value = random.choice(arr)
    print("search '%s' index" % value)
    print("binary search recurse result:", binary_search_recurse(arr, value))
    print("binary search loop result:", binary_search_loop(arr, value))
